package mtest3.day6;

import java.util.ArrayList;
import java.util.Arrays;

public class Demo3 {
    public static void main(String[] args) {

        // 直接插入排序
        int[] arr = new int[]{22, 15, 17, 16, 14, 8, 12, 1, 25, 19, 33};
        insetSort(arr);
        System.out.println(Arrays.toString(arr));
        for (int s : arr) {
            System.out.println(s);
        }

        // 监视哨兵
        int[] arr1 = new int[]{-1, 22, 15, 17, 16, 14, 8, 12, 1, 25, 19, 33};
        insertSortWithGuard(arr1);
        System.out.println(Arrays.toString(arr1));


    }

    // 直接插入排序
    public static void insetSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 把待插入的数据存入临时变量
            int temp = arr[i];

            int j;
            // 当前的数和前面已经排号的数比较大小
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                //  如果当前的数比前一位的数据小，前一位的数据后移一位
                arr[j + 1] = arr[j];
            }
            // 上面的j-- 后,比较值， 不满足条件，跳出循环，将temp 放到 j+1位置
            arr[j + 1] = temp;
        }
    }

    // 带监视哨的插入顺序，注意数组第0个位置不存真实数据，作为监视哨使用
    public static void insertSortWithGuard(int[] arr) {
        for (int i = 2; i < arr.length; i++) {
            // 把待插入的数据临时存入arr[0],arr[0] 为监视哨
            arr[0] = arr[i];
            int j;
            for (j = i - 1; arr[0] < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = arr[0];
        }
    }

    // 选择排序
    public static void SelectSort(int[] arr) {
        // 获取数组长度
        int length = arr.length;
        // 遍历整个数组，0-倒数第二个数据
        for (int i = 0; i < length - 1; i++) {
            // 把i 的下标给min
            int min = i;
            // 遍历后面的所有数据，获取最小值
            for (int j = i + 1; j < length; j++) {
                if (arr[min] > arr[j]) {
                    // 让min 指向最小的下标值
                    min = j;

                }
            }
            // 把最小值 和i位置数据交换
            if (min != i) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }

    }
}
